package offer;

public class offerII_0072 {
    public int mySqrt(int x) {
        if(x==0) return 0;
        int result=  sqrt(x,1,x);
        if(result*result/result!=result||result*result>x) return result-1;
        return result;
    }

    public int sqrt(int x,int left,int right){
        if(left==right) return left;
        int b=left+(right-left)/2;
        if(b*b/b!=b) return sqrt(x,left,b-1);
        if(b*b<x) return sqrt(x,b+1,right);
        return sqrt(x,left,b);
    }
}
